class ListNode {
    val: number
    next: ListNode | null
    constructor(val?: number, next?: ListNode | null) {
        this.val = (val === undefined ? 0 : val)
        this.next = (next === undefined ? null : next)
    }
}
/**
 * https://leetcode-cn.com/problems/design-hashset/
 * 设计哈希集合
 */
class MyHashSet {
    private set: Set<number> = new Set();

    add(key: number): void {
        this.set.add(key)
    }

    remove(key: number): void {
        this.set.delete(key)
    }

    contains(key: number): boolean {
        return this.set.has(key)
    }
}

class MyHashSet2 {
    private root: ListNode | null = null
    private dummyHead = new ListNode(-1, null)

    add(key: number): void {
        // 首次添加, 放到根节点
        if (this.root === null) {
            this.root = new ListNode(key)
            this.dummyHead.next = this.root;
            return
        }

        // 1. 查找是否有重复元素
        let root = this.dummyHead.next,
            prev = this.dummyHead;
        while (root !== null) {
            // 找到了
            if (root.val === key) return;
            prev = root;
            root = root.next;
        }

        // 没找到, 添加到尾部
        prev.next = new ListNode(key, null)
    }

    remove(key: number): void {
        if (this.root === null) return;

        // 从根节点开始找
        let root = this.dummyHead.next,
            prev = this.dummyHead;
        while (root !== null) {
            // 找到了
            if (root.val === key) {
                // 找到了, 将root闪电即可
                prev.next = root.next;

                // 删除的是根节点, 重新修改this.root的指向
                if (root === this.root) {
                    this.root = prev.next;
                }

                // prev不需要修改
            } else {
                prev = root;
            }
            root = root.next;
        }
    }

    contains(key: number): boolean {
        if (this.root == null) return false
        // 从根节点开始找
        let root: ListNode | null = this.root
        while (root !== null) {
            // 找到了
            if (root.val === key) return true;
            root = root.next;
        }

        return false
    }
}


const ms = new MyHashSet
ms.add(1)
ms.add(2)